package Year22_Month05.day20;


import java.util.Deque;
import java.util.LinkedList;

public class 滑动窗口最大值 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new LinkedList<>();//定义一个双端链表用来筛选出最大值
        int len = nums.length;
        int[] arr = new int[len - k + 1];//定义一个刚好可以完全接收当前窗口最大值的数组
        for (int i = 0; i < len; i++) {
            //头：首先就是判断一下当前窗口的大小，如果说当前窗口大于k了，就要丢掉队头的元素
            if(!dq.isEmpty() && i - k + 1 > dq.getFirst()){
                dq.poll();//如果说当前的窗口值过大，就丢弃掉头元素
            }
            //尾：如果说当前要入队的下标对应数组元素，大于当前队尾下标对应数组元素，就把这个队尾元素删除
            while(!dq.isEmpty() && nums[i] > nums[dq.getLast()]){
                dq.pollLast();
            }
            //尾：现在这么一搞之后，就可以确定队首元素对应的下标值为最大
            dq.add(i);
            //头:让arr来记录当前窗口最大值
            if(i >= k - 1){
                arr[i - k + 1] = nums[dq.getFirst()];
            }
        }
        return arr;
    }
}
